/**
 * 图的最小生成树问题(表示一张图可以使用点集合与边集合来表示)
 *
 *
 * 普里姆算法(加点法)
 * - 1.任选一个点作为起点
 * - 2.找到以当前选中点为起点路径最短的边
 * - 3.如果这个边的另一端没有被连通进来,那么就连通
 * - 4.如果这个边的另一端已经被连通进来，那么就跳过
 * - 5.循环2-4直到所有点都被连通
 *
 * 克鲁斯卡尔算法(加边法)
 * - 1.遍历所有边，将边按照权重排序，从最小的边开始
 * - 2.保证连接的两端至少有一个点是新的点或者是将两个不同的集合链接起来
 * - 3.循环1-2直到所有的点都连通
 */

class Node {
  constructor(val) {
    this.val = val;
    this.neighbor = [];
  }
}

const max = 9999;
const pointSets = [new Node('A'), new Node('B'), new Node('C'), new Node('D'), new Node('E')];  // 点集合
const distance = [ // 边集合
  [0, 4, 7, max, max],
  [4, 0, 8, 6, max],
  [7, 8, 0, 5, max],
  [max, 6, 5, 0, 7],
  [max, max, max, 7, 0],
];

/**
 * 获取最小距离的节点
 *
 * 该函数的目的是从给定的点集中找到一个节点，该节点与当前点集中的某个节点之间的距离最小
 * 它可以用于图形算法中，例如寻找最短路径等问题
 *
 * @param {Array} pointSets - 包含所有节点的点集
 * @param {Function} distance - 用于计算两个节点之间距离的函数
 * @param {Array} nowPointSet - 当前考虑的点集，函数将寻找与该集中节点距离最近的节点
 * @returns {Node} - 返回与当前点集中节点距离最近的节点
 */
function getMinDisNode(pointSets, distance, nowPointSet) {
  let collect = {
    start: '', // 开始的点
    end: '', // 结束的点
    num: max, // 距离
  };
  nowPointSet.forEach(item => {
    let startIdx = pointSets.findIndex(i => i.val === item.val);
    distance[startIdx].forEach((val, idx) => {
      let cz = nowPointSet.findIndex(n => {
        return n.val === pointSets[idx].val;
      });
      if (val != 0 && val < collect.num && cz == -1) {
        collect.start = item;
        collect.num = val;
        collect.end = pointSets[idx];
      }
    });
  });
  collect.start && collect.start.neighbor.push(collect.end);
  collect.end && collect.end.neighbor.push(collect.start);
  return collect;
}

/**
 * 实现 Prim 算法来查找图中的最小生成树。
 *
 * @param {Array} pointSets - 表示图的顶点的点集数组。
 * @param {Function} distance - 用于计算两点之间距离的函数。
 * @param {Number} start - pointSets 数组中起始点的索引。
 */
function prim(pointSets, distance, start) {
  let nowPointSet = [];
  nowPointSet.push(start);
  while (nowPointSet.length !== pointSets.length) {
    let minDisNode = getMinDisNode(pointSets, distance, nowPointSet);
    minDisNode.end && nowPointSet.push(minDisNode.end);
  }
  return nowPointSet;
}

//console.log("▶『prim』", prim(pointSets, distance, pointSets[2]));


/**
 * 判断两个节点是否可以连接。
 *
 * 该函数用于确定在给定的一组已链接节点中，两个节点之间是否没有共同的链接关系。
 * 它通过检查两个节点是否未链接到同一个节点来实现这一点。
 *
 * @param {string} startNode - 起始节点
 * @param {string} endNode - 结束节点
 * @param {Array<Array<object>>} linked - 已链接的节点数组，表示一个链接关系
 * @returns {boolean} 如果两个节点可以连接则返回 true，否则返回 false
 */
function canLink(startNode, endNode, linked) {
  let startN = null, endN = null;
  // 遍历已链接的节点数组，查找起始节点和结束节点所在的链接
  linked.forEach((item, index) => {
    if (item.includes(startNode)) startN = linked[index];
    if (item.includes(endNode)) endN = linked[index];
  });
  // 如果两个节点都找到了对应的链接且它们相同，则不能连接；否则可以连接
  return !(startN != null && endN != null && startN == endN);
}


/**
 * 在两个节点之间建立链接关系
 * 如果节点对尚未链接，则创建新的链接；如果已链接，则更新链接
 * @param {Node} startNode - 起始节点
 * @param {Node} endNode - 终止节点
 * @param {Array} linked - 已经链接的节点数组
 */
function link(startNode, endNode, linked) {
  // 初始化起始和终止节点的链接数组为空
  let startN = null, endN = null;
  
  // 遍历已有的链接数组，寻找包含起始节点或终止节点的链接
  linked.forEach((item, index) => {
    if (item.includes(startNode)) startN = linked[index];
    if (item.includes(endNode)) endN = linked[index];
  });
  
  // 根据起始和终止节点的链接情况，决定如何更新或创建链接
  if (startN == null && endN == null) {
    // 如果两者都未链接，创建新的链接
    linked.push([startNode, endNode]);
  } else if (startN != null && endN == null) {
    // 如果起始节点已链接，但终止节点未链接，将终止节点加入起始节点的链接
    startN.push(endNode);
  } else if (startN == null && endN != null) {
    // 如果起始节点未链接，但终止节点已链接，将起始节点加入终止节点的链接
    endN.push(startNode);
  } else if (startN != null && endN != null && startN != endN) {
    // 如果两者都已链接，但属于不同的链接，合并这两个链接
    startN.push(...endN);
    linked.splice(linked.indexOf(endN), 1);
  }
  
  // 更新节点的邻居信息
  startNode?.neighbor.push(endNode);
  endNode?.neighbor.push(startNode);
}


/**
 * Kruskal算法实现最小生成树
 * @param {Array} pointSets - 点的集合，表示图中的所有点
 * @param {Array} distance - 二维数组，表示点与点之间的距离
 * 该函数通过不断选择最小权重的边来构建最小生成树，确保不会形成环路
 */
function kruskal(pointSets, distance) {
  let linked = []; // 当前链接的点集合，用于存储已经连接的点，避免形成环路
  
  while (true) {
    let startNode = '', // 用于记录当前最小距离的开始点
      endNode = '', // 用于记录当前最小距离的结束点
      num = max; // 初始化距离为最大值，用于寻找最小值
    distance.forEach((distanceItem, distanceIdx) => {
      distanceItem.forEach((itemItem, itemIdx) => {
        let tempStart = pointSets[distanceIdx];
        let tempEnd = pointSets[itemIdx];
        // 检查当前距离是否为非零且小于已知最小值，并且两点间未形成环路
        if (itemItem != 0 && itemItem < num && canLink(tempStart, tempEnd, linked)) {
          num = distance[distanceIdx][itemIdx];
          startNode = tempStart;
          endNode = tempEnd;
        }
      });
    });
    // 连接当前找到的最小距离的两点
    link(startNode, endNode, linked);
    // 当所有点都已连接成一个集合时，结束循环
    if (linked.length == 1 && linked[0].length == pointSets.length) break;
  }
}


kruskal(pointSets, distance);
console.log("▶『kruskal』", pointSets);
